﻿using System;
using System.Collections.Generic;

namespace QuickSortAlgorithm
{
    class QuickSortAlgorithm
    {
        struct Position
        {
            public int Left, Right;
            public Position(int left, int right)
            {
                this.Left = left;
                this.Right = right;
            }
        }

        static void PrintResult(int[] numbers)
        {
            foreach (int number in numbers)
            {
                Console.WriteLine("{0} ", number);
            }
            Console.WriteLine();
        }

        static void Swap(int[] numbers, int left, int right)
        {
            int temp = numbers[right];
            numbers[right] = numbers[left];
            numbers[left] = temp;
        }

        static int Partition(int[] numbers, int left, int right)
        {
            int pivot = numbers[left];

            while (true)
            {
                while (numbers[left] < pivot)
                {
                    left++;
                }
                while (numbers[right] > pivot)
                {
                    right--;
                }
                if (left < right)
                {
                    Swap(numbers, left, right);
                }
                else
                {
                    return right;
                }
            }
        }

        static public void QuickSort(int[] numbers, int left, int right)
        {
            if (left >= right)
            {
                return;
            }

            List<Position> list = new List<Position>();
            Position details = new Position(left, right);
            list.Insert(list.Count, details);

            while (true)
            {
                if (list.Count == 0)
                {
                    break;
                }
                left = list[0].Left;
                right = list[0].Right;
                list.RemoveAt(0);

                int pivot = Partition(numbers, left, right);

                if (pivot > 1)
                {
                    details.Left = left;
                    details.Right = pivot - 1;
                    list.Insert(list.Count, details);
                }

                if (pivot + 1 < right)
                {
                    details.Left = pivot + 1;
                    details.Right = right;
                    list.Insert(list.Count, details);
                }
            }
        }

        static void Main()
        {
            int[] numbers = { 10, 3, 5, 2, 1, 8, 6, 4 };

            QuickSort(numbers, 0, numbers.Length - 1);

            PrintResult(numbers);
        }
    }
}